package 剑指Offer.hard;

import java.util.PriorityQueue;
import java.util.Queue;

public class 数据流中的中位数 {
    class MedianFinder {

        Queue<Integer> smalllPriorityQueue = new PriorityQueue<>();//默认实现小顶堆
        Queue<Integer> bigPriorityQueue = new PriorityQueue<>((x, y) -> y - x);//大顶堆

        /**
         * initialize your data structure here.
         */
        public MedianFinder() {

        }

        public void addNum(int num) {
            if (smalllPriorityQueue.size() == bigPriorityQueue.size()) {
                smalllPriorityQueue.add(num);
                bigPriorityQueue.add(smalllPriorityQueue.poll());
            } else {
                bigPriorityQueue.add(num);
                smalllPriorityQueue.add(bigPriorityQueue.poll());
            }
        }

        public double findMedian() {
            return smalllPriorityQueue.size() == bigPriorityQueue.size() ?
                    (smalllPriorityQueue.peek() + bigPriorityQueue.peek()) / 2
                    : bigPriorityQueue.peek();
        }
    }
}
